package _dp_base;

/**
 * 746. 使用最小花费爬楼梯
 */
public class No746 {
    private int[] cost;

    /**
     * 1. 递归
     */
    public int minCostClimbingStairs1(int[] cost) {
        this.cost = cost;
        int n = cost.length;
        return Math.min(dfs(n - 1), dfs(n - 2));
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        return Math.min(dfs(i - 1), dfs(i - 2)) + cost[i];
    }

    /**
     * 2. 迭代
     */
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;

        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            f[i + 2] = Math.min(f[i + 1], f[i]) + cost[i];
        }
        return Math.min(f[n + 1], f[n]);
    }

    /**
     * 3. 空间优化
     */
    public int minCostClimbingStairs3(int[] cost) {
        int f0 = 0, f1 = 0;
        for (int c : cost) {
            int temp = f1;
            f1 = Math.min(f1, f0) + c;
            f0 = temp;
        }
        return Math.min(f1, f0);
    }
}
